1. Field of the Invention
This invention relates generally to error-correction coding in digital communications and storage devices. More specifically, the present invention relates to a method and apparatus for solving the key equation to decode Reed-Solomon (RS) codes utilizing the modified Euclidean algorithm to generate an error location polynomial and an error evaluation polynomial.
2. Description of the Related Art
Bose-Chaudhuri-Hocquenghem (BCH) codes form a large class of powerful random error correcting cyclic codes. Among the nonbinary BCH codes, the most important subclass is the class of Reed-Solomon codes. Reed-Solomon codes are equivalent to a BCH code with the code symbol field being the same as the field of the roots of the code generator polynomial. Reed-Solomon codes have been widely used in digital communications and data storage devices (e.g. compact discs) in such a way that induced errors are efficiently correctable. The most commonly used approach to constructing the Reed-Solomon codes is the generator polynomial construction represented by BCH codes.
The following references, incorporated by reference herein in their entireties, are helpful to achieve a general understanding of the principles of Reed-Solomon codes: (1) Stephen B. Wicker and Vijay K Bhargava, Reed-Solomon Codes and Their Applications, IEEE Press, 1994; (2) E. Dahlman, K. Shu Lin, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications Prentice-Hall, Inc. Englewood Cliffs, N.J., 1983.
Generally, the arithmetic of error correction codes is based on a finite (Galois) field GF(2.sup.m) which is the extension field of GF(2) and is generated by a field generator polynomial f(x) of degree m with binary coefficients (0,1) in GF(2). For example, assuming .alpha. is a primitive element in GF(2.sup.m) satisfying f(.alpha.)=0, then the set {1, .alpha.,.alpha..sup.2, . . . , .alpha..sup.m-1 } is called the standard basis that spans GF(2.sup.m). In field GF(2.sup.m), a primitive element is defined as an element that has order 2.sup.m -1. The order n of an element .alpha. in GF(2.sup.m) is defined as the smallest positive integer such that .alpha..sup.n =1. Any finite field element .beta. can be expressed in the standard basis as EQU .beta.=.beta..sub.0 +.beta..sub.1.alpha.+.beta..sub.2.alpha..sup.2 +. . . +.beta..sub.m-1.alpha..sup.m-1 (1)
where the binary digits {.beta..sub.0, .beta..sub.1, . . . , .beta..sub.m-1 } represent the standard coordinates of .beta..
For convenience, .beta..sub.m-1 is referred to as the most significant bit (MSB) and .beta..sub.0 as the least significant bit (LSB). All arithmetic operations in GF(2.sup.m) are performed by exclusive OR (XOR) gates which perform modulo 2 addition (modulo 2 subtraction is equivalent to addition) and AND gates which perform modulo 2 multiplication.
A Reed-Solomon code (n,k,t) over GF(2.sup.m) can correct up to t error symbols, where GF(2.sup.m) is a finite field with 2.sup.m m-bit symbols, n is the total number of symbols in a code word, k is the number of information symbols in a code word, n-k is the number of check symbols in a code word and t=(n-k)/2.
The RS code is defined by a code generator polynomial G(x) of degree 2t with {1, .alpha., .alpha..sup.2, . . . , .alpha..sup.2t-1 } as its roots. Any legal code word, treated as a polynomial of degree n-1, must be divided by G(x).
The following table represents the RS codes in the digital television standard of the United States Advanced Television Systems Committee (ATSC) and the Standard of Digital Video Broadcasting by Satellite (DVB-S) of the European Telecommunications Standard Institute (ETSI), where m=8 (eight-bit symbol=one byte).
ATSC DVB-S k 187 188 n 207 204 t 10 8 m 8 8
A brief description of the conventional error correcting procedure with regard to a Reed-Solomon code (n,k,t) will be given below. In this description, we assume that R.sub.i, i=0,1,2, . . . ,n-1, are the n received error-corrupted m-bit symbols.
Step (1): Generate 2t syndrome values ##EQU1##
and then, based on these syndrome digits, form a syndrome polynomial S(x) of degree 2t-1 representing the received codeword ##EQU2##
Step (2): Solve the key equation EQU .OMEGA.(x)=.LAMBDA.(x)S(x)mod x.sup.2t (4)
using the modified Euclidean algorithm to generate an error location polynomial .LAMBDA.(x) of degree t and an error evaluation polynomial .OMEGA.(x) of degree t-1;
Step (3): Determine the roots of .LAMBDA.(x) by the Chien search method, each of which indicates an error location. If .alpha..sup.-.mu. is a root of .LAMBDA.(x), there is an error in the received symbol R.sub..mu. and the associated error value is given by the Forney algorithm EQU .OMEGA.(.alpha..sup.-.mu.)/.LAMBDA..sub.odd (.alpha..sup.-.mu.) (5)
where .LAMBDA..sub.odd (x) is the polynomial of preserving the odd terms of .LAMBDA.'(x), the terms associated with {x,x.sup.3,x.sup.5, . . .}.
Step (4): Correct the errors by subtracting the error magnitudes from the received codeword in the associated error locations.
It should be noted that, as used herein, the term "received codeword" refers to a codeword that is either received through a communication medium or reproduced from a storage medium.
The modified Euclidean algorithm for solving the key equation is mathematically described as follows, starting with S(x) generated in accordance with step (1) above: EQU Initialization: A(x)=S(x), A'(x)=1, B(x)=x.sup.2t, B'(x)=0 (6)
Euclidean Iteration:
if deg_A(x)&lt;deg_B(x) then PA1 endif EQU Q=a.sub.lead /b.sub.lead (7) EQU A(x).rarw.A(x)-Q.multidot.B(x).multidot.x.sup.deg.sup..sub.-- .sup.A(x)-deg.sup..sub.-- .sup.B(x) (8) EQU A'(x).rarw.A'(x)-Q.multidot.B'(x).multidot.x.sup.deg.sup..sub.-- .sup.A(x)-deg.sup..sub.-- .sup.B(x) (9) PA1 if deg A(x)&lt;t, then PA1 endif
swap A(x) and B(x) PA2 swap A'(x) and B'(x) PA2 algorithm finished EQU .OMEGA.(x)=A(x) (10) EQU .LAMBDA.(x)=A'(x) (1)
where a.sub.lead represents the leading coefficient of A(x), b.sub.lead represents the leading coefficient of B(x), and "deg" means the degree of polynomial.
The notation .rarw. means "simultaneous assignment upon Euclidean iteration."
As to Q, it is typically obtained by computing the multiplication of EQU Q=a .sub.lead.multidot.INV (12)
where EQU INV=(b.sub.lead).sup.-1 (13)
and the value of INV is typically generated by a look-up table.
A brief description of prior art hardware implementations of a key equation solver for Reed-Solomon codes is given below.
Conventional key equation solvers using parallel multipliers are illustrated by, for example, U.S. Pat. Nos. 4,873,688, 5,170,399, 5,396,502, 5,428,628, 5,442,578, and 5,570,378. In these systems, generally, a global m-bit parallel bus is used to transmit the m-bit quotient value Q, and m-by-m parallel multipliers are used to perform the multiplication function. The parallel multiplier operates in parallel-in parallel-out (PIPO) mode, completes its operation in one clock, and requires m.sup.2 AND gates and at least m.sup.2 XOR gates. Thus, these systems have the disadvantage of incurring large gate counts and requiring an m-bit quotient bus.
Systolic implementations of the key equation solver using parallel multipliers are disclosed in, e.g., U.S. Pat. Nos. 4,958,348 and 5,323,402. In these systems, a set of registers is used for storing A(x), A'(x), B(x), B'(x), INV, Q, deg_A(x), and deg_B(x), while another set of registers is used to pipeline data transfer and perform arithmetic operations. Thus, these systems have the disadvantage of needing extra registers to pipeline data transfer and processing.
In the prior art discussed above, m-by-m parallel multipliers are implemented by an array of m.sup.2 AND gates and m.sup.2 XOR gates such that the required multiplication task is completed in one clock cycle. In general, a key equation solver needs more than 2t multipliers.
One way to reduce the number of gates is to use bit-serial multipliers, each of which needs m sequential clock cycles to complete a multiplication while its gate number is only proportional to m. U.S. Pat. No. 4,845,713 is an example of a bit-serial multiplier configuration providing a key equation solver using parallel-in serial-out (PISO) dual-basis bit-serial multipliers. However, this system has the disadvantage of requiring a basis change; using dual-basis requires extra serial-to-parallel registers and extra circuitry for the basis change between standard basis and dual basis.
FIG. 1 shows a conventional cellular VLSI key equation solver 5 using the modified Euclidean algorithm. The arithmetic computations of equations (8) and (9) are performed using parallel multipliers 6 in a processing unit (PU) 7, which includes m-bit registers REG U(i) and REG L(i), i=1,2, . . . ,2t+2. Other functions for realizing the modified Euclidean algorithm are carried out by processing unit 7. As the modified Euclidean algorithm proceeds, the degrees of A(x) and B(x) decrease while the degrees of A'(x) and B'(x) increase. Register degA and register degB are used to indicate the degrees of A(x) and B(x) respectively. The upper-side m-bit registers U(i), i=1,2, . . . ,degA +1, are used to store the coefficients of A(x). The upper-side m-bit registers U(i), i=degA+2, . . . ,2t+2, are used to store the coefficients of B'(x). The lower-side m-bit registers L(i), i=1,2, . . . .degB+1, are used to store the coefficients of B(x). The lower-side m-bit registers L(i), i=degB+2, . . . ,2t+2, are used to store the coefficients of A'(x). Registers U(1), L(1), U(2t+2), and L(2t+2) represent the leading coefficients of A(x), B(x), B'(x), and A'(x), respectively. The m-bit register REG_Q and the m-bit register REG_INV are used to store the values Q and INV, respectively. In particular, the m-bit register REG_Q produces an m-bit quotient value that is transmitted in parallel by a global m-bit parallel quotient bus 18.
FIG. 2, is a flow chart showing the operations of the key equation solver circuit of FIG. 1. In FIG. 2, S(i), .LAMBDA.(i), and .OMEGA.(i) represent the coefficients of x.sup.i of the syndrome polynomial S(x), the error location polynomial .multidot.(x), and the error evaluation polynomial .OMEGA.(x), respectively.
The INITIALIZATION block 20 represents an algorithm initialization stage in which (1) syndrome polynomial S(x) is assigned to A(x); (2) x.sup.2t is assigned to B(x); (3) degA and degB are set to 2t; (4) A'(x) is set to one; and (5) B'(x) is set to zero. The Euclidean iteration starts in the CONTROL block 22. In decision block 22A, the ending condition is checked to determine whether the modified Euclidean algorithm is completed. If yes, then, in ending block 28, the error location polynomial .LAMBDA.(x) is given by the polynomial A'(x), and the error evaluation polynomial .OMEGA.(x) is given by the polynomial A(x). On the other hand, if decision block 22A determines that the modified Euclidean algorithm is not completed, then the CONTROL block 22 will decide which of ARITH block 24, SHIFT block 25 or SWAP block 26 is to be performed for the present Euclidean iteration.
In the ARITH block 24, the arithmetic computations of equations (8) and (9) are executed. In SHIFT block 25, the contents of registers U(.cndot.) are shifted left by one register position, and the register degA is decreased by one. In SWAP block 26, the contents of registers U(.OMEGA.) and registers L(.cndot.) are swapped, and the registers degA and degB are adjusted accordingly. If ARITH block 24 is performed in the present iteration, U(1) will become zero. Then, in the next iteration, SHIFT block 25 or SWAP block 26 will be performed to adjust the contents of U(.cndot.) and/or L(.cndot.) and to recompute the value of Q.
Due to the implementation of the parallel multipliers, the CONTROL block 22, ARITH block 24, SHIFT block 25, and SWAP block 26 are all completed in one clock cycle.